/*
https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1/
 */
public class Solution330 {
    public int minPatches(int[] nums, int n) {
        int index=0,ans=0;
        long x=1;
        while (x<=n){
            if (index<nums.length && nums[index]<=x){
                x=x+nums[index];
                index++;
            }else{
                x=x*2;
                ans++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution330().minPatches(new int[]{1,3},6));
    }
}
